package cn.cxq.learning.recursion;

import org.junit.jupiter.api.Test;

import java.util.*;

public class AddTarget {
    
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> temp = new ArrayList<>();
    int sum = 0;
    boolean[] visited;

    @Test
    public void test () {
        combinationSum2(new int[]{100,10,20,70,60,10,50}, 80);
    }

    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        
        Arrays.sort(num);
        visited = new boolean[num.length];
        
        dfs (num, target);
        
        return res;
    }
    
    private void dfs (int[] num, int target) {
        if (sum == target) {
            res.add(new ArrayList<>(temp));
            return;
        } else if (sum > target) {
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            sum += num[i];
            temp.add(num[i]);
            dfs(num, target);
            sum -= num[i];
            temp.remove(temp.size() - 1);
            visited[i] = false;
        }
    }
}